package ir;

/**
 * Created by IntelliJ IDEA.
 * User: Admin
 * Date: Apr 21, 2010
 * Time: 2:13:41 PM
 * To change this template use File | Settings | File Templates.
 */
public class SorceReader {

//    public static void main(String[] args) {
//        int i = 0;
//        String[] patern = {"4Sodium", "7mar"};
//        for (String res : patern) {
////            int pos = kmpMatcher("pos: " + Sourse.TEXT, res);
////            System.out.println(Sourse.TEXT.contains(res));
////            System.out.println(pos);
//            i++;
//        }
//
//
//
//    }


    public static int[] prefixFunction(CharSequence s) {
        int n = s.length();
        int[] p = new int[n];
        for (int i = 1; i < n; i++) {
            int k = p[i - 1];
            while (k > 0 && s.charAt(k) != s.charAt(i)) {
                k = p[k - 1];
            }
            p[i] = k + (s.charAt(k) == s.charAt(i) ? 1 : 0);
        }
        return p;
    }

    public static int kmpMatcher(CharSequence s, CharSequence pattern) {
        int m = pattern.length();
        if (m == 0) {
            return 0;
        }
        int n = s.length();
        int[] p = prefixFunction(pattern);

        int k = 0;
        for (int i = 0; i < n; i++) {
            while (k > 0 && s.charAt(i) != pattern.charAt(k)) {
                k = p[k - 1];
            }
            if (s.charAt(i) == pattern.charAt(k)) {
                k++;
            }
            if (k == m) {
                return i - m + 1;
            }
        }
        return -1;
    }


}
